模拟赛题解/2025.10.7 模拟赛

T1-分组（group）

题面

麦克班上一共有 $n$ 个同学（不包括麦克，麦克作为班长，需要将所有同学（除自己以外）划分为若干个小组，以方便管理。

为了让大家尽量满意分组的结果，麦克用独立程度来描述每一个同学，即其希望自己所在小组的人数 $\leq$ 独立程度。

经过观察，麦克得到了每个同学的独立程度，其中第 $i$ 个同学为 $a_i$。

麦克很快分好了组，但他并不满足于此，他希望求出一共有多少种本质不同的分组方式。

这里两组方案本质不同当且仅当存在两个同学，其中一组方案中两人在同一组，而另一种方案中两人不在同一组。

由于答案可能非常大，只需要求出对 $10^9+7$ 取模后的结果。

提示：每个同学需恰在某一组中，且每组均需至少包含一个人。

$1\leq n\leq2000,1\leq a_i\leq n$。

题解

定义 $f_{i,j}$ 表示确定了人数 $\leq i$ 的组且有 $j$ 个 $a_t\geq i$ 的人加入，设有 $x$ 个 $a_t=i$ 和 $y$ 个 $a_t>i$， 转移即

$$\forall t\in\left[\left\lceil\frac{\max(x-j,0)}i\right\rceil,\left\lfloor\frac{x+y-j}i\right\rfloor\right],\frac{(j+it)!}{(j+it-x)!}\frac{f_{i-1,j}}{t!(i!)^t}\rightarrow f_{i,j+it-x}$$

根据调和级数，时间复杂度为 $O(n^2\log n)$。

T2-奇迹（miracle）

题面

阿尔瓦·洛伦兹正在进行着新一轮的电学实验。

他有 $n$ 块质地相同的金属，每块金属已经均匀带上了一定的电荷，电荷量可以是任意实数，初始时，每块金属的比荷都是整数。

阿尔瓦希望通过一些操作使得这 $n$ 块金属的质量和电荷量达到自己的预期，但是他不知道这是否可能实现，于是请你帮助他验证一下。

初始时，第 $i$ 块金属的质量是 $m_i$，比荷是 $a_i$。阿尔瓦希望通过操作使得第 $i$ 块金属的质量仍为 $m_i$，比荷为 $b_i$。

阿尔瓦的操作分为以下两种：

• 将一块金属分割为两部分，使得两部分的质量和等于原来金属的质量；
• 拿起两块金属（不要求相邻）让它们融合，新合成的金属的质量和电荷量是原来两块金属对应物理量的加和。注意比荷不一定是加和，需要重新计算。

你可以认为金属质量和电荷量足够大，是可以被无限分割的，且分割后仍保持均匀带电状态，分成的两部分的比荷不变。

操作可以进行任意次。你需要判断是否存在一种方案使得目标被达成。

$\sum n\leq 10^6,1\leq m_i,a_i,b_i\leq 10^6$。

题解

想象这样一个场景：你手头有一张借记卡（不能欠款），你会不停地收入一些钱，花掉一些钱，当一次消费的金额大于卡内余额的时候，这次消费就不能进行了。

到这个题里，我们也可以开一张「能量借记卡」。

我们将本题的一些概念用金融中的术语表达：$l_i$ 可以认为是第 $i$ 笔账单的数量，$a_i$ 可以认为是每笔账单的支出（因此初态中的第 $i$ 个杯子可以变成 $l_i$ 个单价为 $a_i$ 的商品）；同理，$b_i$ 可以认为是每笔账单的收入（因此终态中的第 $i$ 个杯子可以变成 $l_i$ 张每张票面金额为 $b_i$ 的支票）。

首先将初始状态的 $n$ 个杯子按温度升序排序，终态的 $n$ 个杯子也按温度升序排序。

接下来我们搞两个指针 $p$,$q$，刚开始 $p$ 指向初始态的第一个杯子，$q$ 指向终态的第一个杯子。

我们现在可以用 $q$ 中的支票去买 $p$ 中的商品。当然商家很刁钻，一张支票只能买一个商品。

如果一张支票的金额大于一个商品的钱，我们就可以将多余的钱（或者说是能量）存进银行卡，如果一张支票的金额小于一个商品的钱，我们就需要从银行卡里取些钱（能量）了。

（$p$ 中的商品数和 $q$ 中的支票数可能不一定相等，不过这不是问题，$p$ 空的时候就将 $p$ 向后移动，$q$ 空的时候也将 $q$ 向后移动就行了，别忘了总商品数和总支票数是相等的）

因为我们手里拿的是借记卡，所以任何时候余额都不能为负。

如果我们顺利地走完了上面的整个过程（也就是说没有赊账的情况发生），说明有解。否则无解。

T3-渔猎（fishing）

题面

格蕾丝让杰弗里·博纳维塔给自己创造了一块大小为 $w\times h$，且左右边界、上下边界连通的区域，然后在这个区域里围出了 $n$ 个矩形的闭合水渊。

现在，记忆只有 7 秒钟的格蕾丝有点分不清每个水渊的范围了。她只记得每个水渊 矩形的两个对角顶点。格蕾丝发现，只知道两个对角顶点的情况下每个矩形的可能情况 有不止一种。她想问问你在最好的情况下，同时被n 个水渊包围的面积最大是多少？

$1\leq n\leq 5\times 10^5 , 2\leq w, h\leq 10^9$。

题解

横纵坐标是独立的。

我们发现一对顶点的作用是把 $X$ 和 $Y$ 坐标划分成了两个部分，使得这两个部分不可能同时被覆盖到，且具体覆盖到哪个区域我们可以自己指定。于是开线段树，对值域进行哈希。以 $X$ 坐标为例，若两个顶点的 $X$ 坐标分别是 $p,q(p<q)$，则可知 $[p,q)$ 和 $[0,p)\lor[q,w)$ 必然不可能同时被覆盖，我们需要给它们不同的哈希值。

最后哈希值相同的部分大概率能被一起覆盖，那么分别取 $X,Y$ 坐标里出现次数最多的哈希值，乘起来就行了。

这个大概率是多大呢？如果你用 $32$ 位随机数，这个概率确实不够大，用 $64$ 位随机数就可以了。

T4-影袭（strike）

题面

看到格蕾丝练习洄游，桑格莉娅也想练习一下自己的表演能力。

桑格莉娅准备了一块大小为 $n\times m$ 的空地作为训练场地。

桑格莉娅的一次歌剧表演从左上角 $(0,0)$ 开始，经过若干次距离为 $1$ 的移动后，到右下角 $(n−1,m−1)$ 结束。由于对于效率比较注重，桑格莉娅只会向右或者向下移动。她不能移动到障碍上。

初始时，训练场地是空的。鉴于在空舞台上表演有点简单，桑格莉娅决定给自己上上难度。她准备了 $k$ 次操作，每次操作形如“ 在 $(x,y)$ 位置摆放一个障碍 ”，但她发现有些障碍的摆放可能使得自己接下来无法表演，因此她只会在障碍摆放完后仍然可以进行表演的情况下摆放障碍。对于每次操作，她想知道这次操作是否会因为影响表演而被忽略。

桑格莉娅想和你一起讨论障碍的布置方式，因此这些操作的给出都是在线的，你需 要在她给出一个操作后立刻回答。

$2\leq n,m\leq 10^5,1\leq k\leq 10^6$。

题解

贴模型走路是一个很实用的技巧，可以在这类网格路径题中有效地去除一些重复冗余状态。

比如这道题，定义首末两行、两列为边缘部分，其他为非边缘部分，我们可以发现无论怎么在非边缘部分添加障碍，都存在至少两条合法路径，如下图：

ooooo
o.x.o
oxx.o
ox.xo
ooooo

X 表示障碍，O 表示边缘部分，. 是普通的空地。我们发现只要存在边缘部分，我们就不用管普通的空地。

但是边缘部分可能会改变。比如在一个空的 $5\times5$ 网格中添加一个障碍：

ooox.
o.ooo
o...o
o...o
ooooo

不难发现障碍的作用是“如果处在原来的边缘部分，就把这个边缘部分挪个地方到左下角/右上角”，或者说“如果处在原来的边缘部分，则令自己左下角/右上角不可能再为边缘部分”。到底哪个角就要看自己原先处在左下角的边缘还是右上角的边缘。如果同时处在两类边缘，那说明没有路径可以走了，此时输出 Yes，我们也顺便获得了是否有路径的充要条件。

边缘的修改是可以均摊的，因为每个点最多被一类边缘用一次，于是写一个事件驱动模拟。其中需要找最大最小值，set 常数大，换成懒惰删除的堆就可以了。